package Heap;

import java.util.Arrays;

public class Lesson10Homework {

	public static void main(String[] args) {

		
		int[] arr = {45,98,4,3,87,6,5,7,1,6,8,7,89,8,65,5,78,5,9,3,45,2,7};
		System.out.println(Arrays.toString(arr));
		
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));

	}

	private static void quickSort(int[] arr, int start, int end)
	{
		if(start > end)
		{
			return;
		}
		else
		{
			int storeInd = partition(arr, start, end);
			quickSort(arr, start, storeInd - 1);
			quickSort(arr, storeInd + 1, end);
		}
	}

	public static int partition (int[] arr, int start, int end)
	{
		int pivot = arr[start];
		int storeInd = start + 1;
		
		for(int i = storeInd; i <= end; i++)
		{
			if (arr[i] > pivot)
			{
				swap(arr, i, storeInd);
				storeInd++;
			}
		}
		
		swap(arr, start, storeInd - 1);
		return storeInd - 1;
		
		
		
		
		
	}
	
	
	
	private static void swap(int[] arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
				
		
	}
	
	
	
}
